# source: http://en.wikipedia.org/wiki/Diamond-square_algorithm

# let's assume that we have a square matrix of a given size
size = 2000

matrix = [[-1for j in range(size)] for j in range(size)]

# pick random values for 'the corners' of the matrix
import random

maxrand = 1000

matrix[0][0] = random.randint(0, maxrand)
matrix[0][size-1] = random.randint(0, maxrand)
matrix[size-1][0] = random.randint(0, maxrand)
matrix[size-1][size-1] = random.randint(0, maxrand)
mean1 = -1
mean2 = -1
mean3 = -1
mean4 = -1
mean5 = -1

def mid(up, down, left, right):

    # middleIndex1 and middleIndex2 describe the indices in the middle of the 'sides' of the matrix/square

    middleIndex1 = (left + right)/2
    middleIndex2 = (up + down)/2

    # mean1, mean2, ..., mean5 are the means of the corners:
    #
    # c1.....m1.....c2
    # .      .      .
    # .      .      .
    # .      .      .
    # .      .      .
    # m2.....m5.....m3
    # .      .      .
    # .      .      .
    # .      .      .
    # .      .      .
    # c3.....m4.....c4
    #
    # c1, c2, c3, c4 are the corners, m1, m2, ..., m5 are means 1 - 5

    mean1 = (matrix[up][left] + matrix[up][right])/2

    mean2 = (matrix[up][left] + matrix[down][left])/2

    mean3 = (matrix[up][right] + matrix[down][right])/2

    mean4 = (matrix[down][left] + matrix[down][right])/2

    mean5 = (mean1 + mean4)/2

    matrix[up][middleIndex1] = mean1
    matrix[down][middleIndex1] = mean4
    matrix[middleIndex2][left] = mean2
    matrix[middleIndex2][right] = mean3
    matrix[middleIndex2][middleIndex1] = mean5

    if not(((left - right) == -1) or ((left - right) == 1)):

        # calling order while dividing:
        # *********
        # * 1 * 2 *
        # *********
        # * 3 * 4 *
        # *********

        # 1
        mid(up, middleIndex2, left, middleIndex1)
        # 2
        mid(up, middleIndex2, middleIndex1, right)
        # 3
        mid(middleIndex2, down, left, middleIndex1)
        # 4
        mid(middleIndex2, down, middleIndex1, right)


mid(0, (size-1), 0, (size-1))

#for row in matrix:
    #print row

print 'random numbers: ', matrix[0][0], matrix[0][size-1], matrix[size-1][0], matrix[size-1][size-1]

## optional - representation via matplotlib
#import matplotlib.pyplot as plt
#
#plt.imshow(matrix)
#plt.show()
